package org.example.top40;


import java.util.ArrayList;
import java.util.List;

public class main34 {
    //复原IP地址
    //输入：s = "101023"
    //输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
    //参数：字符串s，起始位置startIndex，逗点数量pointNum
    //终止：逗点为3，并验证第四段是否合法在加入res
    //单层逻辑：fori用来在哪个位置画逗号，验证这一段是否合法，合法截取加‘，’ 递归i+2，回溯pointNum--删‘，’
    //是否合法：start>end 以0开头并且start！=end 大于2+55的不合法 fori构造数字，途中检查字符是否合法，大于255
    //易错点：加入点s = s.substring(0, i + 1) + "." + s.substring(i + 1); 和回溯删除点s=s.substring(0,i+1)+s.substring(i+2);
    static List<String> res=new ArrayList<>();
    public static void main(String[] args) {
        String s="101023";
        List<String> res = restoreIpAddresses(s);
        System.out.println(res);
    }
    private static List<String> restoreIpAddresses(String s){
        int startIndex=0;
        int pointNum=0;
        dfs(s,startIndex,pointNum);
        return res;
    }

    private static void dfs(String s, int startIndex, int pointNum) {
        if(pointNum==3){
            if(isvalid(s,startIndex,s.length()-1)){
                res.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if(isvalid(s,startIndex,i)){
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointNum++;
                dfs(s,i+2,pointNum);
                pointNum--;
                s=s.substring(0,i+1)+s.substring(i+2);
            }else {
                break;
            }
        }
    }

    private static boolean isvalid(String s, int start, int end) {
        if(start>end){
            return false;
        }
        if(s.charAt(start)=='0'&&start!=end){
            return false;
        }
        int num=0;
        for (int i = start; i <=end ; i++) {
            if(s.charAt(i)<'0'||s.charAt(i)>'9'){
                return false;
            }
            num=num*10+(s.charAt(i)-'0');
            if(num>255){
                return false;
            }
        }
        return true;
    }
}
